#include "../tools.h"


class TimeMap {
public:
    unordered_map<string, vector<int>> tmap;
    unordered_map<string, vector<string>> kmap;

    /** Initialize your data structure here. */
    TimeMap() {

    }
    
    void set(string key, string value, int timestamp) {
        tmap[key].emplace_back(timestamp);
        kmap[key].emplace_back(value);

    }
    
    string get(string key, int timestamp) {
        vector<int> vt = tmap[key];
        vector<string> vk = kmap[key];

        if(vt.size() == 0) return "";
        if(timestamp < vt[0]) return "";
        if(timestamp > vt.back()) return vk.back();

        int i = 0, j = vt.size() - 1, m;
        while(i < j){
            m = (i + j) / 2;
            if(vt[m] == timestamp) return vk[m];
            if(vt[m] < timestamp) i = m;
            if(vt[m] > timestamp) j = m;
        }
        return vk[i];

    }
};

int main(int argc, char const *argv[])
{
    TimeMap kv;
    kv.set("foo", "bar", 1);    // 存储键 "foo" 和值 "bar" 以及时间戳 timestamp = 1   
    kv.get("foo", 1);           // 输出 "bar"   
    kv.get("foo", 3);           // 输出 "bar" 因为在时间戳 3 和时间戳 2 处没有对应 "foo" 的值，所以唯一的值位于时间戳 1 处（即 "bar"）   
    kv.set("foo", "bar2", 4);
    kv.get("foo", 4);           // 输出 "bar2"   
    kv.get("foo", 5);           // 输出 "bar2"


    
    return 0;
}
